//
// Created by francklinson on 2021/5/25.
//
#include <vector>
#include <iostream>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &nums) {
        int n = (int) nums.size();
        return dfs(nums, 0, n - 1);
    }

    TreeNode *dfs(vector<int> &nums, int left, int right) {
        if (left >= right) return nullptr;
        int mid = (left + right) / 2;
        auto root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;

    }
};

int main() {
    vector<int> v{-10, -3, 0, 5, 9};
    Solution sol;
    sol.sortedArrayToBST(v);
    return 0;
}